001 /* EVolve - an Extensible Software Visualization Framework
002 * Copyright (C) 2001-2002 Qin Wang
003 *
004 * This library is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Library General Public
006 * License as published by the Free Software Foundation; either
007 * version 2 of the License, or (at your option) any later version.
008 *
009 * This library is distributed in the hope that it will be useful,
010 * but WITHOUT ANY WARRANTY; without even the implied warranty of
011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012 * Library General Public License for more details.
013 *
014 * You should have received a copy of the GNU Library General Public
015 * License along with this library; if not, write to the
016 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017 * Boston, MA 02111-1307, USA.
018 */
019
020 /*
021 * EVolve is distributed at http://www.sable.mcgill.ca/EVolve/
022 */
023
024 package EVolve.util;
025
026 import EVolve.data.*;
027
028
029 public class Sorter implements Cloneable{
030 private int[] source, target;
031 private EntityComparator comparator;
032
033 public Sorter(Entity[] array, EntityComparator comparator) {
034 this.comparator = comparator;
035
036 int size = array.length;
037 Entity[] arr = new Entity[size];
038
039 source = new int[size];
040 target = new int[size];
041
042 for (int i = 0; i < size; i++) {
043 arr[i] = array[i];
044 source[i] = i;
045 }
046
047 mergesort(arr);
048
049 for (int i = 0; i < size; i++) {
050 target[source[i]] = i;
051 }
052 }
053
054 public int getTarget(int source) {
055 if ((source >= target.length) || (source < 0))
056 return -1;
057 else
058 return target[source];
059 }
060
061 public int getSource(int target) {
062 if ((target >= source.length) || (target < 0))
063 return -1;
064 else
065 return source[target];
066 }
067
068 private void mergesort(Entity[] array) {
069 Entity[] temp = new Entity[array.length];
070 int[] tempSource = new int[array.length];
071
072 int step = 1;
073 while (step<array.length) {
074 int L1=0, L2, H1, H2, k=0;
075 while (L1+step<array.length) {
076 L2 = L1 + step;
077 H1 = L2 - 1;
078 if (L2+step-1>=array.length)
079 H2 = array.length-1;
080 else
081 H2 = L2+step-1;
082 k = mergepass(temp,array,tempSource,L1,L2,H1,H2,k);
083 L1 = H2 + 1;
084 }
085 int i = L1;
086 while ((k < array.length)&&(i<array.length)) {
087 temp[k] = array[i];
088 tempSource[k] = source[i];
089 i++; k++;
090 }
091 for (i=0; i<array.length; i++) {
092 array[i] = temp[i];
093 source[i] = tempSource[i];
094 }
095 step = step * 2;
096 }
097 }
098
099 private int mergepass(Entity[] temp, Entity[] array, int[] tempSource, int L1, int L2, int H1, int H2, int k) {
100 int i = L1, j = L2;
101 while ((i<=H1)&&(j<=H2)) {
102 if (comparator.compare(array[i], array[j]) < 0) {
103 tempSource[k] = source[i];
104 temp[k] = array[i];
105 i++;
106 } else {
107 tempSource[k] = source[j];
108 temp[k] = array[j];
109 j++;
110 }
111 k++;
112 }
113 while (i<=H1) {
114 temp[k] = array[i];
115 tempSource[k] = source[i];
116 i++; k++;
117 }
118 while (j<=H2) {
119 temp[k] = array[j];
120 tempSource[k] = source[j];
121 j++; k++;
122 }
123 return k;
124 }
125
126 public Object clone() {
127 Sorter o = null;
128 try {
129 o = (Sorter)super.clone();
130 } catch (CloneNotSupportedException e) {
131 e.printStackTrace();
132 }
133
134 o.source = new int[source.length];
135 for (int i=0; i<source.length; i++)
136 o.source[i] = source[i];
137
138 o.target = new int[target.length];
139 for (int i=0; i<target.length; i++)
140 o.target[i] = target[i];
141
142 o.comparator = (EntityComparator)comparator.clone();
143 return o;
144 }
145 }